//
//  Problem49.swift
//  TestProject
//
//  Created by 毕武侠 on 2021/3/25.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 49. 字母异位词分组 与面试10.02同一个题
 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。

 示例:
 输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
 输出:
 [
   ["ate","eat","tea"],
   ["nat","tan"],
   ["bat"]
 ]
 说明：
 所有输入均为小写字母。
 不考虑答案输出的顺序。
 */
@objcMembers class Problem49: NSObject {
    func solution() {
        print(groupAnagramsSort(["eat", "tea", "tan", "ate", "nat", "bat"]))
        print(groupAnagramsSort(["bdddddddddd","bbbbbbbbbbc"]))
    }
    
    /*
     方式一：
     将每一个字符串 转换成一个另外一个字符串
     1: 创建一个数组array[26], 然后遍历字符串，将每个字符对应的位置上+1
     2: 然后把这个数组转换成字符[0,1,0,3....] => 0103....
     3: 创建一个字典dic[String: [String]]
     4: 假如转换后的字符串，在dic中，则dic[str].append[oldstr], 不在dic[str] = [oldstr]
     5: 得到dic的values即可
     
     */
    func groupAnagrams(_ strs: [String]) -> [[String]] {
        var dic:[String: [String]] = [:]
        for str in strs {
            var array = Array(repeating: 0, count: 26)
            for c in str {
                array[Int(c.asciiValue!) - 97] += 1
            }
            print(array)
            let nStr = array.reduce("") { (str, i) -> String in
                return str + String(i) + ","
            }
            print(nStr)
            if dic[nStr] == nil {
                dic[nStr] = [str]
            } else {
                dic[nStr]!.append(str)
            }
        }
        
        return Array(dic.values)
    }
    
    /*
     方式二：
     将每一个字符串 转换成一个另外一个字符串，通过排序的方式
     1: 创建一个字典dic[String: [String]]
     2: 假如转换后的字符串，在dic中，则dic[str].append[oldstr], 不在dic[str] = [oldstr]
     3: 得到dic的values即可
     
     */
    func groupAnagramsSort(_ strs: [String]) -> [[String]] {
        var dic:[String: [String]] = [:]
        for str in strs {
            let nStr = String(str.sorted())
            if dic[nStr] == nil {
                dic[nStr] = [str]
            } else {
                dic[nStr]!.append(str)
            }
        }
        
        return Array(dic.values)
    }
    
}
